/**
 * \file    parser.cpp
 * \brief   Parser generator.
 * \author  Jérôme LAURENS
 * \version 0.1
 * \date    September 17, 2014
 *
 * Reads a LALR(1) grammar, generates a parser based on a template file.
 * This is based on lemon parser generator, but has strongly been
 * revisited.
 *
 */

#include <boost/algorithm/string.hpp>
#include <iterator>
#include <regex>
#include "parser.h"

LPP_NAMESPACE_BEGIN

::std::ostream& operator<< (std::ostream &out, StringList const & list) {
    for (String const & s: list) {
        out << s;
    }
    return out;
}

::std::regex operator "" _regex(const char * s, size_t num_chars) {
    return std::regex(String(s,num_chars));
}

const String Parser::here_str        ("^");
const String Parser::special_str     (here_str+"\\s*%\\s*");
const String Parser::macro_str       ("([[:alpha:]_][[:alnum:]_]*)");
const String Parser::terminal_str    ("([[:upper:]][[:alnum:]_]*)");
const String Parser::non_terminal_str("([[:lower:]][[:alnum:]_]*)");
const String Parser::symbol_str      ("([[:alpha:]][[:alnum:]_]*)");
const String Parser::alias_str       ("(\\$[[:alnum:]_]+)?");
const String Parser::key_str         ("('.')");
const String Parser::post_precedence_str    ("!");
const String Parser::post_associativity_str    ("(?:(<)|(=)|(>))");
const Regex Parser::comment_rx        (special_str+"%");
const Regex Parser::ifdef_rx          (special_str+"ifdef\\b");
const Regex Parser::ifndef_rx         (special_str+"ifndef\\b");
const Regex Parser::ifdef_or_ifndef_rx(special_str+"ifn?def\\b");
const Regex Parser::else_rx           (special_str+"else\\b");
const Regex Parser::endif_rx          (special_str+"endif\\b");
const Regex Parser::define_rx         (special_str+"define\\b");
const Regex Parser::undef_rx          (special_str+"undef\\b");
const Regex Parser::macro_rx          (here_str+"\\s+"+macro_str+"\\b");
const Regex Parser::start_rx          (special_str+"start\\b");
const Regex Parser::shortcut_rx       (special_str+"shortcut\\b");
const Regex Parser::wildcard_rx       (special_str+"wildcard\\b");
const Regex Parser::prec_rx           (special_str+"prec\\b");
const Regex Parser::left_rx           (special_str+"left\\b");
const Regex Parser::right_rx          (special_str+"right\\b");
const Regex Parser::nonassoc_rx       (special_str+"nonassoc\\b");
const Regex Parser::fallback_rx       (special_str+"fallback\\b");
const Regex Parser::continuation_rx  (here_str+"\\s+(?!%)");
const Regex Parser::terminal_rx      (here_str+"\\s+"+terminal_str);
const Regex Parser::non_terminal_rx  (here_str+"\\s+"+non_terminal_str);
const Regex Parser::lhs_rx           (here_str+non_terminal_str+alias_str+"\\s*::=\\s*");
const Regex Parser::non_lhs_rx       (here_str+terminal_str+alias_str+"\\s*");
const Regex Parser::rhs_rx           (here_str+"\\s*(?:"+symbol_str+"|"+key_str+")"+alias_str+"\\s*");
const Regex Parser::rhs_multi_rx     (here_str+"(?:\\s*(?:"+symbol_str+"|"+key_str+")"+"\\s*\\|)+\\s*(?:"+symbol_str+"|"+key_str+")"+alias_str+"\\s*");
const Regex Parser::more_rhs_rx      (here_str+"\\s+(?:"+symbol_str+"|"+key_str+")"+alias_str+"\\s*");
const Regex Parser::key_rx                  (here_str+"\\s+"+key_str);
const Regex Parser::terminal_or_key_rx      (here_str+"(?:"+terminal_str+"|"+key_str+")\\s*");
const Regex Parser::more_terminal_or_key_rx (here_str+"\\s+(?:"+terminal_str+"|"+key_str+")\\s*");
const Regex Parser::sharp_rx                (here_str+"\\s*#\\");
const Regex Parser::cpp_comment_rx          (here_str+"\\s*//");
const Regex Parser::cpp_comment_or_eol_rx   (here_str+"\\s*(?://|$)");
const Regex Parser::class_rx                (special_str+"(?:class|token_class)\\b");
const Regex Parser::equals_rx               (here_str+"\\s*::=\\s*");
const Regex Parser::or_terminal_or_key_rx   (here_str+"\\s*(?:\\||/)\\s*(?:"+terminal_str+"|"+key_str+")");
const Regex Parser::more_rx                 (here_str+"\\s*&\\s*");
const Regex Parser::precedence_rx    (here_str+"\\s*\\[\\s*(?:"+terminal_str+"|"+key_str+")\\s*\\]");
const Regex Parser::post_precedence_rx    (here_str+"\\s*"+post_precedence_str+"\\s*");
const Regex Parser::post_associativity_rx    (here_str+"\\s*"+post_associativity_str+"\\s*");

bool Parser::get_next_line() {
    // DEBUG_MESSAGE("message: get_next_line");
    if (input_m) {
        line = "";
        while (std::getline(*input_m,line)) {
            ++line_number_m;
            if (!line.empty()) {
                begin_m = line.cbegin();
                end_m = line.cend();
                if (!match(comment_rx)) {
                    // DEBUG_MESSAGE("line %lu: %s", line_number_m, line.c_str());
                    feed_action_stack();
                    return true;
                }
            }
        }
    }
    return false;
}

bool Parser::match(const std::regex & rx) {
    if (std::regex_search(begin_m, end_m, result_m, rx)) {
        begin_m = result_m[0].second;
        // DEBUG_MESSAGE("match %zu->%s", line.length()-std::distance(begin_m,end_m), String(result_m[0].first,result_m[0].second).c_str());
        return true;
    } else {
        return false;
    }
}
String Parser::whole_match() {
    return result_m.size()>0?result_m[0].str():"";
}
String Parser::first_match() {
    return result_m.size()>1?result_m[1].str():"";
}
String Parser::second_match() {
    return result_m.size()>2?result_m[2].str():"";
}
String Parser::third_match() {
    return result_m.size()>3?result_m[3].str():"";
}
String Parser::symbol_match() {
    String symbol = first_match();
    if (symbol.empty()) {
        String K = second_match();
        if (grammar()->has_symbol_for_shortcut(K)) {
            symbol = grammar()->symbol_for_shortcut(K)->name();
        } else {
            error()<<"Define shortcut "<<K<<" prior to its use."<<std::endl;
        }
    }
    return symbol;
}

#ifdef LPP_CONTAINS
#error choose another name
#endif
#define LPP_CONTAINS(__CONTAINER,__OBJECT)\
    ([this](){auto C=__CONTAINER;\
            return std::find (C.begin(), C.end(), __OBJECT)!=C.end();}())

#ifdef LPP_IS_DEFINED
#error choose another name
#endif

#define LPP_IS_DEFINED(__NAME)\
    (!__NAME.empty() && defines_m.find(__NAME)!=defines_m.cend())

#ifdef LPP_IF_PUSH
#error change that name
#endif
#define LPP_IF_PUSH(__A,__L)\
    if_actions_s.push(ActionIndex(std::bind(&__self::__A,this),__L))
#ifdef LPP_IF_POP
#error change that name
#endif
#define LPP_IF_POP \
    if_action = if_actions_s.top(); \
    if_actions_s.pop

#ifdef LPP_PUSH
#error change that name
#endif
#define LPP_PUSH(__A,__L)\
    actions_s.push(ActionIndex(std::bind(&__self::__A,this),__L))
#ifdef LPP_POP
#error change that name
#endif
#define LPP_POP \
    action = actions_s.top(); \
    actions_s.pop

Index Parser::parse() {
    // DEBUG_MESSAGE("message: parse");
    line_number_m = number_of_errors_m = 0;
    if (get_next_line()) {
        LPP_IF_PUSH(preprocess,line_number_m);
        do {
            LPP_IF_POP();
            if (if_action.first) {
                if_action.first();
            } else {
                throw std::logic_error("The if action stack must be filled with non void actions.");
            }
        } while (get_next_line() && !if_actions_s.empty());
        if (!line.empty()) {
            throw std::logic_error("The if action stack must contain at least a preprocess action.");
        }
        while(!if_actions_s.empty()) {
            LPP_IF_POP();
            if_action.first();
        }
        while(!actions_s.empty()) {
            LPP_POP();
            action.first();
        }
    }
    if (!number_of_errors_m
            && setup_accept_rule()
            && accept_non_terminals()
            && sort_symbols()) {
        grammar_m->setup_rule_precedences();
    }
#ifndef NDEBUG
    {
        if (grammar()->number_of_lookahead_symbols()!=
                grammar()->number_of_terminals()
                + grammar()->number_of_non_terminals()) {
            std::logic_error("Inconsistent number of symbols.");
        }
        DEBUG_MESSAGE("========== SET OF SYMBOLS:");
        SymbolRefList Ss(grammar()->symbols().begin(),grammar()->symbols().end());
        std::sort(Ss.begin(),Ss.end(),
                  [](SymbolRef const & lhs, SymbolRef const & rhs)->bool{
            return lhs<rhs;
        });
        for (SymbolRef const & symbol: Ss) {
            DEBUG_MESSAGE("%s",Description()(symbol).c_str());
        }
        DEBUG_MESSAGE("========== SET OF SYMBOLS BY NAME AND SHORT NAME:");
        for (SymbolRef const & symbol: Ss) {
            DEBUG_MESSAGE("%s<=>%s",symbol->name().c_str(),symbol->short_name().c_str());
        }
        DEBUG_MESSAGE("========== SET OF RULES:");
        for (RuleRef const & rule: grammar()->rules()) {
            DEBUG_MESSAGE("%s",Description()(rule,0).c_str());
        }
        DEBUG_MESSAGE("========== LONG DESCRIPTIONS OF RULES:");
        for (RuleRef const & rule: grammar()->rules()) {
            DEBUG_MESSAGE("%s",Description()(rule,3).c_str());
        }
    }
#endif
#ifndef NDEBUG
        if (number_of_errors_m>0) {
            DEBUG_MESSAGE("========== ERROR ========== ERROR ========== ERROR ==========");
            DEBUG_MESSAGE("========== NUMBER OF ERRORS WHILE PARSING: %ld",number_of_errors_m);
            DEBUG_MESSAGE("========== ERROR ========== ERROR ========== ERROR ==========");
        }
#endif
    return number_of_errors_m;
}

bool Parser::proceed_if_controls() {
    // DEBUG_MESSAGE("message: proceed_if_controls");
    String macro;
    if(match(ifdef_rx)) {
        if_actions_s.push(if_action);
        if (match(macro_rx)) {
            macro = first_match();
        } else {
            error()<<"Missing macro name after %ifdef keyword."<<std::endl;
        }
        // once the balancing %endif will be parsed, we will continue parsing.
        // but in the meanwhile, we must close the %if group
        if (LPP_IS_DEFINED(macro)) {
            LPP_IF_PUSH(preprocess_until_else_or_required_endif,line_number_m);
        } else {
            LPP_IF_PUSH(preprocess_since_else_until_required_endif,line_number_m);
        }
    } else if(match(ifndef_rx)) {
        if_actions_s.push(if_action);
        // same as before, but swap cases
        if (match(macro_rx)) {
            macro = first_match();
        } else {
            error()<<"Missing macro name after %ifndef keyword."<<std::endl;
        }
        // once the balancing %endif will be parsed, we will continue parsing.
        // but in the meanwhile, we must close the %if group
        if (LPP_IS_DEFINED(first_match())) {
            LPP_IF_PUSH(preprocess_since_else_until_required_endif,line_number_m);
        } else {
            LPP_IF_PUSH(preprocess_until_else_or_required_endif,line_number_m);
        }
    } else if (match(define_rx)) {
        if (match(macro_rx)) {
            defines_m.insert(first_match());
        } else {
            error()<<"Missing macro name after %define keyword."<<std::endl;
        }
    } else if (match(undef_rx)) {
        if (match(macro_rx)) {
            defines_m.erase(first_match());
        } else {
            error()<<"Missing macro name after %undef keyword."<<std::endl;
        }
    } else {
        return false;
    }
    return true;
}

bool Parser::preprocess_until_else_or_required_endif() {
    // DEBUG_MESSAGE("message: preprocess_until_else_or_required_endif");
    if (proceed_if_controls()) {
    } else if (match(else_rx)) {
        LPP_IF_PUSH(require_endif,action.second);
    } else if (match(endif_rx)) {
        // found
    } else {
        if_actions_s.push(if_action);
        return proceed();
    }
    return true;// one line has been consumed
}

bool Parser::preprocess_until_required_endif() {
    // DEBUG_MESSAGE("message: preprocess_until_required_endif");
    if (match(endif_rx)) {
        // found
    } else {
        String macro;
        if (match(else_rx)) {
            if_actions_s.push(if_action);
            error()<<"No previous %ifn?def for %else."<<std::endl;
        } else if(proceed_if_controls()) {
            ; // done
        } else {
            if_actions_s.push(if_action);
            return proceed();
        }
    }
    return true;
}

bool Parser::require_endif() {
    // DEBUG_MESSAGE("message: require_endif");
    if (line.empty()) {
        error()<<"Missing %endif to match line "<<action.second<<"."<<std::endl;
    } else if (match(endif_rx)) {
        // found
    } else {
        if_actions_s.push(if_action);
        if(match(ifdef_or_ifndef_rx)) {
            if (!match(macro_rx)) {
                error()<<"Missing macro name after %ifdef keyword."<<std::endl;
            }
            LPP_IF_PUSH(require_endif,line_number_m);
        }
    }
    return true;// one line has been consumed
}

bool Parser::preprocess_since_else_until_required_endif() {
    // DEBUG_MESSAGE("message: preprocess_since_else_until_required_endif");
    if (match(else_rx)) {
        LPP_IF_PUSH(preprocess_until_required_endif,action.second);
    } else if (match(endif_rx)) {
        // found
    } else {
        if_actions_s.push(if_action);// gobble
        if(match(ifdef_or_ifndef_rx)) {
            if (!match(macro_rx)) {
                error()<<"Missing macro name after %ifdef keyword."<<std::endl;
            }
            LPP_IF_PUSH(require_endif,action.second);
        }
    }
    return true;// one line has been consumed
}

bool Parser::proceed() {
    // DEBUG_MESSAGE("message: proceed");
    while(!actions_s.empty()) {
        LPP_POP();
        if (action.first()) {// one line has been consumed
            // DEBUG_MESSAGE("One line has been consumed.");
            return true;
        }
    }
    return false;
}

bool Parser::preprocess() {
    // DEBUG_MESSAGE("message: preprocess");
    if (proceed_if_controls()) {
        // next
    } else if (match(else_rx)) {
        if_actions_s.push(if_action);
        error()<<"No previous %ifn?def for %else."<<std::endl;// here is the difference
    } else if (match(endif_rx)) {
        if_actions_s.push(if_action);
        error()<<"No previous  %ifn?def for %endif."<<std::endl;// here is the difference
    } else if (!line.empty()) {
        if_actions_s.push(if_action);
        return proceed();
    }
    return begin_m==end_m;
}

void Parser::feed_action_stack() {
    // DEBUG_MESSAGE("message: feed_action_stack");
    switch (actions_s.size()) {
    case 0:
        // DEBUG_MESSAGE("feed: proceed_other_if_any");
        LPP_PUSH(proceed_other_if_any,line_number_m);
    case 1:
        // DEBUG_MESSAGE("feed: proceed_wildcard_if_any");
        LPP_PUSH(proceed_wildcard_if_any,line_number_m);
    case 2:
        // DEBUG_MESSAGE("feed: proceed_class_if_any");
        LPP_PUSH(proceed_class_if_any,line_number_m);
    case 3:
        // DEBUG_MESSAGE("feed: proceed_fallback_if_any");
        LPP_PUSH(proceed_fallback_if_any,line_number_m);
    case 4:
        // DEBUG_MESSAGE("feed: proceed_start_if_any");
        LPP_PUSH(proceed_start_if_any,line_number_m);
    case 5:
        // DEBUG_MESSAGE("feed: proceed_shortcut_if_any");
        LPP_PUSH(proceed_shortcut_if_any,line_number_m);
    case 6:
        // DEBUG_MESSAGE("feed: proceed_precedence_if_any");
        LPP_PUSH(proceed_precedence_if_any,line_number_m);
    case 7:
        // DEBUG_MESSAGE("feed: proceed_reduction_if_any");
        LPP_PUSH(proceed_reduction_if_any,line_number_m);
    default:
        ;
    }
    // DEBUG_MESSAGE("size: %lu",actions_s.size());
}

bool Parser::match_precedence(Symbol::Associativity::Value & associativity) {
    return (match(left_rx) && ((associativity=Symbol::Associativity::LEFT),true))
            || (match(right_rx) && ((associativity=Symbol::Associativity::RIGHT),true))
            || (match(nonassoc_rx) && ((associativity=Symbol::Associativity::NONE),true));
}

bool Parser::require_precedence_continued() {
    // DEBUG_MESSAGE("message: proceed_precedence_continued");
    if (match(continuation_rx)) {
        return complete_precedence();
    } else {
        error()<<"Missing continuation line."<<std::endl;
    }
    return true;
}

bool Parser::complete_precedence() {
    // DEBUG_MESSAGE("message: complete_precedence");
    if (match(more_terminal_or_key_rx)) {
        do {
            String const symbol = symbol_match();
            if (!symbol.empty()) {
                SymbolRef sR = grammar_m->symbol_for_name(symbol);
                if (sR->has_precedence()) {
                    error()<< "Symbol \""<<symbol<<"\" has already been given a precedence("<<sR->precedence()<<"."<<std::endl;
                } else {
                    sR->precedence(++precedence_m);
                    sR->associativity(associativity_m);
                }
            }
        } while (match(more_terminal_or_key_rx));
        if (match(non_terminal_rx)) {
            error()<<"Only terminal symbols may have precedence ("<<first_match()<<")."<<std::endl;
            feed_action_stack();
        } else if (match(more_rx)) {
            LPP_PUSH(require_precedence_continued,action.second);
        }
    } else if (match(more_rx)) {
        LPP_PUSH(require_precedence_continued,action.second);
    } else if (begin_m != end_m) {
        feed_action_stack();
        std::cout << std::string(begin_m,end_m) << std::endl;
        std::cout << line << std::endl;
        error()<<"Only terminal symbols may have precedence."<<std::endl;
    } else {
        feed_action_stack();
        error()<<"Missing at least one terminal symbol."<<std::endl;
    }
    return true;
}

bool Parser::proceed_precedence_if_any() {
    // DEBUG_MESSAGE("message: proceed_precedence_if_any");
    associativity_m = Symbol::Associativity::UNKNOWN;
    if (match_precedence(associativity_m)) {
        feed_action_stack();
        return complete_precedence();
    }
    return begin_m==end_m;
}

bool Parser::proceed_start_if_any() {
    // DEBUG_MESSAGE("message: proceed_start_if_any");
    if (match(start_rx)) {
        feed_action_stack();
        if (match(non_terminal_rx)) {
            grammar_m->set_start_symbol_name(first_match());
        } else {
            error()<<"Missing a non terminal symbol after %start keyword."<<std::endl;
        }
        return true;
    }
    return false;
}

bool Parser::proceed_shortcut_if_any() {
    // DEBUG_MESSAGE("message: proceed_shortcut_if_any");
    if (match(shortcut_rx)) {
        feed_action_stack();
        if (match(key_rx)) {
            String const K = first_match();
            if (grammar()->has_symbol_for_shortcut(K)) {
                error()<<"The shortcut is already used."<<std::endl;
            } else if (match(terminal_rx)) {
                String const symbol = first_match();
                grammar()->symbol_for_name(symbol,K);
            } else {
                error()<<"Missing the terminal symbol after "<<K<<"."<<std::endl;
            }
        } else {
            error()<<"Missing a shortcut key ('.') after %shortcut keyword."<<std::endl;
        }
        return true;
    }
    return false;
}

bool Parser::proceed_wildcard_if_any() {
    // DEBUG_MESSAGE("message: proceed_shortcut_if_any");
    if (match(wildcard_rx)) {
        feed_action_stack();
        if (grammar()->wildcard_symbol()->name()!="*") {
            error()<<"Only one %wildcard per grammar is expected."<<std::endl;
        } else if (match(more_terminal_or_key_rx)) {
            grammar()->wildcard_symbol(symbol_match());
        } else {
            error()<<"Missing a Terminal after %wildcard keyword."<<std::endl;
        }
        return true;
    }
    return false;
}

bool Parser::proceed_other_if_any() {
    // DEBUG_MESSAGE("message: proceed_other_if_any");
    if (match(cpp_comment_rx)) {
        feed_action_stack();
        return true;
    }
    return begin_m==end_m;
}

bool Parser::proceed_other() {
    // DEBUG_MESSAGE("message: proceed_other");
    if (line.empty()) {
    } else if (match(non_lhs_rx)) {
        error() << "Only non terminal symbols as lhs of reduction rules." << std::endl;
    } else {
        error() << "Unsupported line format: " << line << std::endl;
    }
    return true;
}

#ifdef __Sectioning__
#pragma mark === %class ===
#endif

bool Parser::proceed_class_if_any() {
    // DEBUG_MESSAGE("message: proceed_class_if_any");
    if (match(class_rx)) {
        feed_action_stack();
        if (match(non_terminal_rx)) {
            String lhs = first_match();
            symbol_m = grammar_m->symbol_for_name(lhs);
            if (symbol_m->is_multi_terminal()) {
                error()<<"Already defined as %class: "<< lhs <<std::endl;
            }
            if (!match(equals_rx)) {
                error()<<"Missing ::= symbol after %class id ..."<<std::endl;
            }
            LPP_PUSH(require_class_rhs,action.second);
            return false;
        } else {
            error()<<"Missing non terminal symbol after %class."<<std::endl;
            return true;
        }
    }
    return false;
}

bool Parser::complete_class_rhs() {
    // DEBUG_MESSAGE("message: complete_class_rhs");
    String rhs = first_match();
    SymbolRef S = grammar_m->symbol_for_name(rhs);
    symbol_m->add_sub_symbol(S);
    LPP_PUSH(complete_class_more_rhs,line_number_m);
    return false;
}

bool Parser::require_class_rhs() {
    // DEBUG_MESSAGE("message: require_class_rhs");
    if (match(terminal_or_key_rx)) {
        return complete_class_rhs();
    } else if (match(more_rx)) {
        LPP_PUSH(require_class_rhs_continued,action.second);
    } else {
        error()<<"Missing terminal symbol after %class id ::= ..."<<std::endl;
    }
    return true;
}

bool Parser::complete_class_more_rhs() {
    // DEBUG_MESSAGE("message: complete_class_more_rhs");
    if (match(more_rx)) {
        LPP_PUSH(require_class_rhs_continued,action.second);
        return true;
    } else if (match(or_terminal_or_key_rx)) {
        String rhs = first_match();
        SymbolRef S = grammar_m->symbol_for_name(rhs);
        symbol_m->add_sub_symbol(S);
        LPP_PUSH(complete_class_more_rhs,line_number_m);
    } else if (match(more_terminal_or_key_rx)) {
        String rhs = first_match();
        SymbolRef S = grammar_m->symbol_for_name(rhs);
        symbol_m->add_sub_symbol(S);
        LPP_PUSH(complete_class_more_rhs,line_number_m);
    }
    return false;
}

bool Parser::require_class_rhs_continued() {
    // DEBUG_MESSAGE("message: require_class_rhs_continued");
    if (match(continuation_rx)) {
        LPP_PUSH(require_class_rhs,action.second);
    } else {
        error()<<"Missing continuation line"<<std::endl;
        return true;
    }
    return false;
}

bool Parser::proceed_fallback_if_any() {
    // DEBUG_MESSAGE("message: proceed_fallback_if_any");
    if (match(fallback_rx)) {
        feed_action_stack();
        if (match(terminal_rx)) {
            String lhs = first_match();
            symbol_m = grammar_m->symbol_for_name(lhs);
            if (symbol_m->is_multi_terminal()) {
                error()<<"Already defined as %fallback: "<< lhs <<std::endl;
            }
            if (match(equals_rx)) {
                LPP_PUSH(require_fallback_rhs,action.second);
                return false;
            } else {
                error()<<"Missing ::= symbol after %fallback id ..."<<std::endl;
            }
        } else {
            error()<<"Missing terminal symbol after %fallback."<<std::endl;
        }
        return true;
    }
    return begin_m==end_m;
}
bool Parser::require_fallback_rhs() {
    // DEBUG_MESSAGE("message: require_fallback_rhs");
    if (match(terminal_or_key_rx)) {
        grammar()->symbol_for_name(symbol_match())->fallback(symbol_m);
        LPP_PUSH(complete_fallback_more_rhs,line_number_m);
        return false;
    } else if (match(more_rx)) {
        LPP_PUSH(require_fallback_rhs_continued,action.second);
        return true;
    } else {
        error()<<"Missing terminal symbol after %fallback ID ::= ..."<<std::endl;
        return true;
    }
}
bool Parser::complete_fallback_more_rhs() {
    // DEBUG_MESSAGE("message: complete_fallback_more_rhs");
    if (match(more_rx)) {
        LPP_PUSH(require_fallback_rhs_continued,action.second);
        return true;
    } else if (match(or_terminal_or_key_rx)
            || match(terminal_or_key_rx)) {
        grammar()->symbol_for_name(symbol_match())->fallback(symbol_m);
        LPP_PUSH(complete_fallback_more_rhs,line_number_m);
    }
    return false;
}
bool Parser::require_fallback_rhs_continued() {
    // DEBUG_MESSAGE("message: require_fallback_rhs_continued");
    if (match(continuation_rx)) {
        LPP_PUSH(require_fallback_rhs,action.second);
        return false;
    } else {
        error()<<"Missing continuation line"<<std::endl;
        return true;
    }
}

bool Parser::proceed_reduction_if_any() {
    // DEBUG_MESSAGE("message: proceed_reduction_if_any");
    if (match(lhs_rx)) {
        feed_action_stack();
        const SymbolRef lhs = grammar_m->symbol_for_name(first_match());
        alias = second_match();
        if (alias.empty()) {
            alias = "$$";
        }
        rule_m = grammar()->new_rule(lhs,alias,line_number_m);
        should_translate_m = false;
        LPP_PUSH(proceed_reduction_template_code_if_any,line_number_m);
        LPP_PUSH(complete_reduction_rhs_if_any,line_number_m);
        return false;
    }
    return begin_m==end_m;
}

bool Parser::complete_reduction_rhs() {
    // DEBUG_MESSAGE("message: complete_reduction_rhs");
    String symbol = symbol_match();
    if (!symbol.empty()) {
        alias = third_match();
        // we must not use the same alias twice
        if (rule_m->lhs_alias() == alias || LPP_CONTAINS(rule_m->rhs_aliases(),alias)) {
            error()<< "Symbol aliases in one production rule must be unique."<<std::endl;
            alias = "";
        }
        SymbolRef & S = grammar_m->symbol_for_name(symbol);
        rule_m->add_rhs_symbol(S,alias);
        if (!S->is_rhs()) {
            S->is_rhs(true);
            if (S->is_multi_terminal()) {
                for (SymbolRef const & symbol: S->get_sub_symbols()) {
                    if (symbol) {
                        symbol->is_rhs(true);
                    }
                }
            }
        }
        if (!S->is_terminal()) {
            complete_post_precedence_if_any(S);
            complete_post_associativity_if_any(S);
            complete_post_precedence_if_any(S);// trick to allow precedence and associativity declarations commutation
        }
    }
    return false;
}
bool Parser::complete_post_associativity_if_any(SymbolRef & S) {
    if (match(post_associativity_rx)) {
        if (S->associativity()==Symbol::Associativity::UNKNOWN) {
            if(first_match().size()) {
                S->associativity(Symbol::Associativity::LEFT);
            } else if(second_match().size()) {
                S->associativity(Symbol::Associativity::RIGHT);
            } else {
                S->associativity(Symbol::Associativity::NONE);
            }
        } else {
            error()<< "Associativity already given."<<std::endl;
        }
    }
    return false;
}
bool Parser::complete_post_precedence_if_any(SymbolRef & S) {
    if (match(post_precedence_rx)) {
        if (rule_m->precedence_symbol()) {
            error()<< "Precedence already given."<<std::endl;
        }
        if (!S->has_precedence()) {
            S->precedence(++precedence_m);
        }
        rule_m->precedence_symbol(S);
    }
    return false;
}
bool Parser::complete_reduction_rhs_multi() {
    // DEBUG_MESSAGE("message: complete_reduction_rhs_multi");
    String multi = whole_match();
    if (!multi.empty()) {
        // DEBUG_MESSAGE("New multi symbol: <%s>",multi.c_str());
        std::regex r = "\\s*\\|\\s*|\\s+"_regex;
        std::sregex_token_iterator iter(multi.begin(), multi.end(),
           r , -1);
        std::sregex_token_iterator end;
        StringList L(iter,end);
        if (L.front().empty()) {
            L.pop_front();
        }
        if (L.back().empty()) {
            L.pop_back();
        }
        String back = L.back();
        L.pop_back();
        std::ostringstream oss;
        for (String const & s: L) {
            oss << s << "|";
        }
        r = "\\s*\\$\\s*|\\s+"_regex;
        iter = std::sregex_token_iterator(back.begin(), back.end(),
           r , -1);
        StringList bL(iter,end);
        if (bL.front().empty()) {
            bL.pop_front();
        }
        if (!bL.empty()) {
            back = bL.front();
            bL.pop_front();
        }
        oss<<back;
        multi=oss.str();
        L.push_back(back);
        SymbolRef const & S = grammar()->symbol_for_name(multi);
        S->is_rhs(true);
        for (String const & s: L) {
            SymbolRef const & SS = grammar()->symbol_for_name(s);
            S->add_sub_symbol(SS);
            SS->is_rhs(true);
        }
        // DEBUG_MESSAGE("New multi symbol: %s",multi.c_str());
        // DEBUG_MESSAGE("%s",Description()(S).c_str());
        alias = bL.empty()?"":String("$")+bL.front();
        // DEBUG_MESSAGE("alias: %s",alias.c_str());
        // we must not use the same alias twice
        if (rule_m->lhs_alias() == alias || LPP_CONTAINS(rule_m->rhs_aliases(),alias)) {
            error()<< "Symbol aliases in one production rule must be unique."<<std::endl;
            alias = "";
        }
        rule_m->add_rhs_symbol(S,alias);
    }
    return false;
}

bool Parser::complete_reduction_rhs_if_any() {
    // DEBUG_MESSAGE("message: complete_reduction_rhs_if_any");
    if (match(rhs_multi_rx)) {
        LPP_PUSH(complete_reduction_rhs_if_any,action.second);
        return complete_reduction_rhs_multi();
    } else if (match(rhs_rx)) {
        LPP_PUSH(complete_reduction_rhs_if_any,action.second);
        return complete_reduction_rhs();
    } else if (match(more_rx)) {
        LPP_PUSH(require_reduction_more_rhs_continued,action.second);
        return true;
    } else if (match(precedence_rx)) {
        String symbol = symbol_match();
        if (rule_m->precedence_symbol()) {
            error()<< "Precedence already given."<<std::endl;
        }
        SymbolRef & S = grammar_m->symbol_for_name(symbol);
        if (!S->has_precedence()) {
            S->precedence(++precedence_m);
        }
        rule_m->precedence_symbol(S);
        return true;
    } else if (match("^\\s*\\["_regex)) {
        error()<< "Precedence symbol must be a terminal."<<std::endl;
        return true;
    } else if (begin_m!=end_m && !match(comment_rx)) {
        error()<< "Syntax error."<<std::endl;
        return true;
    }
    return begin_m==end_m;
}

bool Parser::require_reduction_more_rhs_continued() {
    // DEBUG_MESSAGE("message: require_reduction_more_rhs_continued");
    if (match(continuation_rx)) {
        if (match(rhs_multi_rx)) {
            LPP_PUSH(complete_reduction_rhs_if_any,action.second);
            return complete_reduction_rhs_multi();
        } else if (match(rhs_rx)) {
            LPP_PUSH(complete_reduction_rhs_if_any,action.second);
            return complete_reduction_rhs();
        } else if(match(more_rx)){
            LPP_PUSH(require_reduction_more_rhs_continued,action.second);
            return true;
        } else {
            error()<<"Expecting rhs of reduction rule."<<std::endl;
        }
    } else {
        error()<<"Expecting continuation line."<<std::endl;
    }
    return true;
}

bool Parser::proceed_reduction_template_code_if_any() {
    // DEBUG_MESSAGE("message: proceed_reduction_template_code_if_any");
    if (match(sharp_rx) || match(cpp_comment_rx)) {
        rule_m->add_code_template_line(line);
        LPP_PUSH(proceed_reduction_template_code_if_any,action.second);
        return true;
    } else if (match(continuation_rx)) {
        rule_m->add_code_template_line(line);
        if (!match(cpp_comment_rx)) {
            should_translate_m = should_translate_m || std::distance(begin_m,end_m)!=0;
        }
        LPP_PUSH(proceed_reduction_template_code_if_any,action.second);
        return true;
    } else if (grammar()->add_rule(rule_m)) {
        if (should_translate_m) {
            should_translate_m = false;
            rule_m->translate_template_code(*this);
        }
    } else {
        error()<<"A rule must no appear more than once: line "<<rule_m->rule_line()<<std::endl;
    }
    return begin_m==end_m;
}

#undef LPP_PUSH
#undef LPP_POP
#undef LPP_IF_PUSH
#undef LPP_IF_POP
#undef LPP_CONTAINS
#undef LPP_IS_DEFINED

String Parser::escaped_string_4_regex(String const & __s) {
    String s = std::regex_replace(__s
         , std::regex("([\\^\\$\\\\\\.\\*\\+\\?\\(\\)\\[\\]\\{\\}\\|])")
         , "\\$1");
    return s+"(?![[:alnum:]]|_)";
}

void Rule::translate_template_code(Parser & parser) {
    SymbolRefList list = rhs_symbols();
    list.push_front(lhs_symbol());
    bool lhs_used = false;
    typedef StringList::size_type Size;
    std::map<Size,bool> rhs_used;
    // substitute the longest alias first
    // first record the alias by index in a map
    std::map<String,Size> sesaila_shr;
    Size i=0;
    for (auto const & alias: rhs_aliases_m) {
        rhs_used[i] = false;
        sesaila_shr[alias]=i++;
    }
    // order the aliases, longest first
    StringList ordered_aliases = rhs_aliases_m;
    std::sort(ordered_aliases.begin(), ordered_aliases.end(),
        [](String const &a, String const &b) {
             return a.length()>b.length();
        }
   ) ;
    // replace
    bool should_test_lhs = true;
    StringList translated_lines = code_template_lines_m;
    while (!ordered_aliases.empty()) {
        String alias = ordered_aliases.front();
        if (should_test_lhs && alias.length()<lhs_alias_m.length()) {
            should_test_lhs = false;
            StringList code_lines;
            String replace("LEMONPP_LHS");
            for (String & line: translated_lines) {
                std::string::size_type pos = 0;
                while ((pos = line.find(lhs_alias_m, pos)) != std::string::npos) {
                    lhs_used = true;
                    line.replace(pos, lhs_alias_m.length(), replace);
                    pos += replace.length();
                }
                code_lines.push_back(line);
            }
            translated_lines = code_lines;
        }
        if (alias.empty()>0) {
            break;
        } else {
            ordered_aliases.pop_front();
            StringList code_lines;
            i = sesaila_shr[alias];
            std::ostringstream oss;
            oss<<"LEMONPP_RHS(-"<<rhs_symbols_m.size()-i<<")";
            String replace = oss.str();
            for (String & line: translated_lines) {
                std::string::size_type pos = 0;
                while ((pos = line.find(alias, pos)) != std::string::npos) {
                    rhs_used[i] = true;
                    line.replace(pos, alias.length(), replace);
                    pos += replace.length();
                }
                code_lines.push_back(line);
            }
            translated_lines = code_lines;
        }
    }
    if (should_test_lhs) {
        should_test_lhs = false;
        StringList code_lines;
        String replace("LEMONPP_LHS");
        for (String & line: translated_lines) {
            std::string::size_type pos = 0;
            while ((pos = line.find(lhs_alias_m, pos)) != std::string::npos) {
                lhs_used = true;
                line.replace(pos, lhs_alias_m.length(), replace);
                pos += replace.length();
            }
            code_lines.push_back(line);
        }
        translated_lines = code_lines;
    }
    code_lines_m = translated_lines;
    /* Check to make sure the LHS has been used */
    bool show_code = false;
    if (!lhs_used && lhs_alias_m!="$$") {
        show_code = true;
        parser.error(rule_line_m)<<"Unused alias in production rule: "<<lhs_symbol()->name()<<lhs_alias_m<<std::endl;
    }
    /* Check to make sure the RHS has been used */
    for (auto & pair: rhs_used) {
        auto i = pair.first;
        if (!pair.second && !std::regex_match(rhs_aliases_m[i],std::regex("^\\$\\d+$"))) {
            show_code = true;
            SymbolRef sR = rhs_symbols()[i];
            parser.error()<<"Unused alias in production rule: "<<sR->name()
                      <<rhs_aliases_m[i]<<std::endl;
        }
    }
    if (show_code) {
        std::cout << "Faulty code:" << std::endl;
        for (String const & line: code_template_lines_m) {
            std::cout << line << std::endl;
        }
        for (String const & line: code_lines_m) {
            std::cout << line << std::endl;
        }
    }
}

bool Parser::accept_non_terminals() {
    bool yorn = true;
    for (SymbolRef const & symbol: grammar_m->non_terminals()) {
        if (0==symbol->number_of_rules()) {
            error()<<"Every non terminal must be the lhs of a production rule: "
                  <<symbol->name()<<"."<<std::endl;
            yorn = false;
        }
    }
#ifndef NDEBUG
    for (SymbolRef const & symbol: grammar_m->symbols()) {
        if ((symbol->is_terminal()==symbol->is_non_terminal())==symbol->is_multi_terminal()) {
            // this is OK;
        } else {
            throw std::logic_error("Symbol type is not consistent.");
        }
    }
#endif
    return yorn;
}

bool Parser::sort_symbols() {
    Index i = 1;
    for (SymbolRef const & symbol: grammar_m->terminals()) {
        if (symbol==grammar_m->eof_symbol()) {
            symbol->index(0);
        } else {
            symbol->index(i++);
        }
    }
#ifdef WITH_ERROR_SYMBOL
    grammar_m->error_symbol()->index(i++);
#endif
    for (SymbolRef const & symbol: grammar_m->non_terminals()) {
        symbol->index(i++);
    }
#ifndef NDEBUG
    if (grammar()->number_of_lookahead_symbols()!= i) {
        std::logic_error("Inconsistent number of symbols.");
    }
#endif
#ifdef WITH_DEFAULT_SYMBOL
    grammar_m->default_symbol()->index(i++);
#endif
    for (SymbolRef const & symbol: grammar_m->multi_terminals()) {
        symbol->index(i++);
    }
    return true;
}

bool Parser::setup_accept_rule() {
    // the start symbol of the grammar has eventually been set while parsing a %start line.
    // if this is not the case, we must find a non terminal symbol.
    // in both situations the first symbol must not appear in the rhs.
    SymbolRef start = grammar()->start_symbol();
    if (!start) {
        throw std::logic_error("Missing start symbol in the grammar.");
    }
    DEBUG_MESSAGE("Start symbol: %s",start->name().c_str());
    SymbolRef const & S = grammar()->accept_symbol();
    RuleRef const & R = grammar()->new_rule(S,"$$",0);
    R->add_rhs_symbol(start);
    R->add_rhs_symbol(grammar()->eof_symbol());
    return grammar()->add_rule(R);
}

LPP_NAMESPACE_END

